Ask a child for the biggest number they know, then say "plus one". You have just done mathematics. You did not check every number. You gave a short argument that works for all of them, and no list could ever match it. That move, certainty about something endless from a few steps of reasoning, is what a first mathematics course is really about.
It is also a little frightening, because it asks what the steps are allowed to be. What counts as a legal move? What are numbers made of? Is there a largest infinity? Around 1900 mathematicians found that the loose answers they had used for centuries produced actual contradictions, and rebuilt the ground floor. What they built, and the discovery in 1931 that the building can never be finished, is what this course teaches.
A graduate does not carry the axioms around. A graduate carries a feel for what a proof is, for which statements are slippery, and for the fact that "infinite" is not one thing.
A set is a collection of things, and the only question you may ask about a set is which things are in it. Order does not matter, repeats do not matter. {1, 2, 3} and {3, 2, 1, 1} are the same set. That sounds too thin to build anything on, yet by 1900 almost all of mathematics had been rewritten in the language of sets: a function is a set of input-output pairs, a number can be a set (zero is the empty set, one is the set containing the empty set, and so on), a shape is a set of points.
The first surprise is how fast sets multiply. A subset is a collection you can form by picking some of a set's elements. For each element there are two choices, in or out, and the choices are independent. So a set with n elements has
Five elements give 32 subsets; ten give 1,024; a mere 30 give over a billion. The collection of all subsets of S is the power set of S, and it will matter again when we reach infinity. Switch elements in and out below; each choice of in/out is a binary number, which is why the count is a power of two.
Without JavaScript: a set with 4 elements has 2 × 2 × 2 × 2 = 16 subsets, including the empty set and the whole set. With 6 elements there are 64.
A proof is a chain of statements, so the first skill is reading one exactly. Two phrases carry most of the weight. "For all" (∀) claims something about every member; one counter-example kills it. "There exists" (∃) claims at least one member works; one example proves it. And the order you write them in changes the meaning.
"Everybody loves somebody" is: for every person, there is someone they love. "Somebody is loved by everybody" is: there is one person, whom all love. The first can be true while the second is false, if everyone loves a different person. The reverse never happens. This is the exact trap in the definition of a limit (next course): "for every ε there is a δ" is not the same as "there is a δ that works for every ε", and confusing them is how false proofs happen.
Two more habits. To negate a statement, flip the quantifiers and negate the end: the opposite of "everybody loves somebody" is "somebody loves nobody". And an implication "if P then Q" is only broken by P true and Q false; it is equivalent to its contrapositive, "if not Q then not P" ("if the grass is dry, it did not rain"). Many proofs are easier backwards. Make your own relation below.
Rows love columns. Press a cell to change it.
Without JavaScript: if Ann loves Bo, Bo loves Cy, Cy loves Dee and Dee loves Ann, then everybody loves somebody, but nobody is loved by everybody. If all four love Dee, both statements are true.
The most powerful single move in mathematics is to assume the opposite of what you want and watch it fall apart. Two proofs, both over 2,000 years old, show how it feels. Euclid gave the first in his Elements; the second is traditionally credited to the early Greek mathematicians.
Infinitely many primes. Suppose, for contradiction, you had a complete list of primes. Multiply them all together and add 1; call it N. Divide N by any prime on your list and the remainder is 1, because the product part divides evenly. So no prime on the list divides N. But every number above 1 has some prime factor (that is the quiet fact the proof leans on), so a prime outside your list exists. The list was not complete. The trick is the "+1": it manufactures a number your list cannot reach. Note that N itself need not be prime; the proof only says a new prime divides it.
The square root of 2 is irrational. Suppose √2 = p/q in lowest terms. Then p² = 2q², so p² is even, so p is even, say p = 2r. Then 4r² = 2q², so q² = 2r² and q is even too. Both even contradicts "lowest terms". The trick is choosing lowest terms first, so that a shared factor of 2 is forbidden.
Pick the primes on your "complete" list. The page multiplies them, adds 1, and factors the result.
Without JavaScript: the primes 2, 3, 5, 7, 11, 13 multiply to 30,030, so N = 30,031. It is not divisible by any of them; it equals 59 × 509, two primes your list missed.
Two sets are the same size if you can pair their elements one to one, with none left over on either side. That is how a child checks that every guest has a chair. Applied to infinite sets it gives strange results: the even numbers pair with all the counting numbers (2n with n), so there are "as many" evens as numbers. A set you can list as a first, second, third... item is called countable. The whole numbers, the integers and even the fractions are countable.
In 1891 Georg Cantor published a short argument that the real numbers are not. Take any supposed list of infinite sequences of 0s and 1s (think: which numbers are in each set). Build a new sequence by going down the diagonal and flipping each entry: it differs from the first sequence in the first place, from the second in the second place, and so on. It cannot be anywhere on the list. The trick is making the new object disagree with the n-th item at the n-th place, so it differs from everything at once.
Read each row of the grid as a subset of {1, ..., n}, and the argument becomes Cantor's theorem: no list of subsets of S, indexed by the elements of S, can contain every subset. The missing one is D = {x : x is not in its own row}. That works for any set at all, so the power set is always strictly bigger, and there is no largest infinity. The proof is the same one you can run on a finite grid.
Each row is a subset of {1..n}: a filled cell means that number is in it. Press cells to edit. The bottom row is the diagonal, flipped.
Without JavaScript: write any 3 rows of 3 bits. Flip the diagonal. The new row differs from row 1 in column 1, from row 2 in column 2, from row 3 in column 3, so it is not any of them, however you filled the rows.
Cantor's names for the sizes: the countable infinity is ℵ0 ("aleph-null"); the reals have size 2ℵ0, which is bigger. Whether anything sits between them is the continuum hypothesis, and we will get to what happened to that question.
Early set theory allowed any rule to define a set: "the set of all things that are red", "the set of all sets". Around 1901 Bertrand Russell asked about the set R of all sets that do not contain themselves. Is R a member of itself? If yes, then it is a set that contains itself, so by its own rule it should be out. If no, it is a set that does not contain itself, so it should be in. Either way, a contradiction. It is the barber who shaves exactly those men who do not shave themselves: who shaves the barber?
The rule: the barber shaves every man who does not shave himself, and nobody else. Guess, then test.
Without JavaScript: if the barber shaves himself, the rule says he shaves only men who do not, so he must not. If he does not, the rule says he must. There is no such barber, and there is no such set.
Gottlob Frege, who had just finished the first great attempt to base arithmetic on logic, received Russell's letter at the worst moment. The repair that most of mathematics now uses is Zermelo–Fraenkel set theory (ZF, or ZFC with the axiom of choice). Zermelo's 1908 system replaced "any rule makes a set" with a safer one, separation: given a set A you may carve out the members satisfying a rule, but you cannot conjure a set out of thin air. Then {x in A : x not in x} is fine; it just turns out not to be a member of A. Fraenkel and Skolem sharpened the system in 1922 and added replacement. Its main ingredients, in plain words:
| Axiom | What it lets you do |
|---|---|
| Extensionality | Sets with the same members are the same set. |
| Pairing, Union | Form {a, b}; gather the members of members. |
| Power set | All subsets of a set form a set. |
| Infinity | An infinite set exists (the counting numbers). |
| Separation, Replacement | Carve out by a rule; swap members for their images. |
| Foundation | No set contains itself, and no endless descending chain of memberships. |
| Choice | From any family of non-empty sets you can pick one from each. |
The axiom of choice is the one that has history. It is needed for many theorems (every vector space has a basis) and also gives weird ones, like the Banach–Tarski paradox of 1924, which cuts a ball into pieces that reassemble into two balls the same size. The pieces are not measurable, so nothing physical is violated. Most mathematicians accept it; constructive mathematicians, who insist on explicit constructions, do not. A graduate knows which of their proofs use it.
David Hilbert hoped for a single formal system strong enough for all of mathematics, provably free of contradiction, and able to decide every statement. In 1931 Kurt Gödel showed that this cannot be had. His first incompleteness theorem: any consistent system that can express basic arithmetic, and whose axioms can be listed by a computer program, has true statements it cannot prove. His second: such a system cannot prove its own consistency.
The sketch has three steps, and the first is the one to see. The trick is to turn statements into numbers. Give each symbol a code, and encode a formula by raising successive primes to those codes. Now a statement about formulas is a statement about numbers, which the system can express. Second, with some work, "this number codes a proof of that formula" becomes an arithmetic statement. Third, build a sentence G that says, via the coding, "I am not provable". If the system proves G, it proves something false (assuming it is sound). If it does not, then G is true and unprovable. Try the coding yourself.
Without JavaScript: with the codes 0→1, S→2, +→3, =→4, the formula "0=0" is 21 × 34 × 51 = 810. Factor 810 and you can read the formula back.
Gödel's result did not make mathematics unreliable. It said the foundations are never "finished". And it has a concrete sibling. The continuum hypothesis says nothing lies between the size of the counting numbers and the size of the reals. Gödel showed in 1940 that ZFC cannot disprove it (assuming ZFC is consistent); Paul Cohen showed in 1963, with a new method called forcing, that ZFC cannot prove it either. Set theorists still disagree about what that means: some hope a compelling new axiom will settle it, and others think it has no single true answer. As far as anyone can tell, the answer is not in the axioms we have.
Two more statuses so you can tell open from closed. Closed: the incompleteness theorems and the independence of CH are proved. Open: whether any natural new axiom decides CH. And the earliest question we asked, whether ZFC itself is consistent, cannot be proved inside ZFC (if it is consistent), by Gödel's second theorem.
Mathematics rests on three things you can now see: sets as the raw material, logic with its careful "for all" and "there exists", and proof as the only way to reach certainty about the endless. They explain the surprises (more than one infinity, a set that cannot exist) and the limit (no finite list of rules decides everything).
Try this: this week, take any "always" or "never" claim you hear ("nobody reads anymore") and negate it exactly. Notice that the negation only needs one example.
Sources. Set counting, quantifier logic, Euclid's primes argument, the √2 proof and Cantor's diagonal/Cantor's theorem are standard textbook mathematics (Hammack; Enderton). Cantor's diagonal paper: 1891. Russell's paradox c. 1901, Zermelo's 1908 axioms using separation, and Fraenkel and Skolem's 1922 addition of replacement: Stanford Encyclopedia of Philosophy and the MacTutor biographies. Gödel 1931 (incompleteness); Gödel 1938–40 (CH consistent with ZFC); Cohen 1963 (CH independent, forcing): standard accounts; sources differ slightly on Gödel's exact year (announced 1938–39, monograph 1940). Banach–Tarski 1924. Course: MIT OCW 24.118 (Spring 2019). Every number the interactives show was computed in node: 2n subsets for n=1..6; 2·3·5·7·11·13+1 = 30031 = 59×509; 810 = 2×34×5.